package interview;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

public class interview_17_18 {
    public int[] shortestSeq(int[] big, int[] small) {
        int shortestStart = -1;
        int shortestLength = Integer.MAX_VALUE;
        Map<Integer, Integer> counts = new HashMap<Integer, Integer>();
        int m = big.length, n = small.length;
        for (int i = 0; i < n; i++) {
            int num = small[i];
            counts.put(num, -1);
        }
        int meets = 0;
        int start = 0, end = 0;
        while (end < m) {
            int curr = big[end];
            if (counts.containsKey(curr)) {
                counts.put(curr, counts.getOrDefault(curr, 0) + 1);
                if (counts.get(curr) == 0) {
                    meets++;
                }
            }
            while (meets == n) {
                if (end - start + 1 < shortestLength) {
                    shortestStart = start;
                    shortestLength = end - start + 1;
                }
                int prev = big[start];
                if (counts.containsKey(prev)) {
                    counts.put(prev, counts.get(prev) - 1);
                    if (counts.get(prev) < 0) {
                        meets--;
                    }
                }
                start++;
            }
            end++;
        }
        return shortestStart < 0 ? new int[0] : new int[]{shortestStart, shortestStart + shortestLength - 1};
    }

}
